package primary.primary0;

public class S0213打家劫舍II {

    /**
     * 100, 44 看答案的，优雅一点
     * 也是两种情况，第一种是第一个偷了，最后一个没偷，第二种是第一个没偷，不管最后一个偷没偷
     * 其中1偷n不偷的情况，可以认为，没了最后一个点
     * 1不偷n随便的情况，可以认为没有了第一个节点
     */
    class Solution2{
        public int rob(int[] nums){
            return Math.max(rob(nums, 0, nums.length - 2), rob(nums, 1, nums.length - 1));
        }

        public int rob(int[] nums, int start, int end){
            if(start >= nums.length - 1 || end <= 0 || start >= end){
                return 0;
            }
            int curRob = 0;
            int curUnRob = 0;
            int preRob = 0;
            int preUnRob = 0;
            for(int i = start; i <= end; i++){
                curRob = preUnRob + nums[i];
                curUnRob = Math.max(preRob, preUnRob);
                preRob = curRob;
                preUnRob = curUnRob;
            }
            return Math.max(curRob, curUnRob);
        }
    }


    /**
     * 答案的，差不多。
     */
    class Solution3 {
        public int rob(int[] nums) {
            int length = nums.length;
            if (length == 1) {
                return nums[0];
            } else if (length == 2) {
                return Math.max(nums[0], nums[1]);
            }
            return Math.max(robRange(nums, 0, length - 2), robRange(nums, 1, length - 1));
        }

        public int robRange(int[] nums, int start, int end) {
            int first = nums[start], second = Math.max(nums[start], nums[start + 1]);
            for (int i = start + 2; i <= end; i++) {
                int temp = second;
                second = Math.max(first + nums[i], second);
                first = temp;
            }
            return second;
        }
    }


    /**
     * 100，6
     */
    class Solution {
        /**
         * 分成两部分，一部分是第一个偷了，一部分是第一个没偷，岂不美哉
         */
        public int rob(int[] nums) {
            if (nums == null || nums.length == 0) {
                return 0;
            }
            if (nums.length == 1) {
                return nums[0];
            }
            // 不止有一个房子
            return Math.max(firstStealed(nums), firstUnStealed(nums));

        }

        private int firstStealed(int[] nums) {
            int curStealed = 0;
            int curUnStealed = 0;
            int preStealed = nums[0];
            int preUnStealed = 0;

            for (int i = 1; i < nums.length; i++) {
                curStealed = Math.max(preUnStealed + nums[i], preStealed);
                curUnStealed = Math.max(preStealed, preUnStealed);
                preStealed = curStealed;
                preUnStealed = curUnStealed;
            }
            return curUnStealed;
        }

        private int firstUnStealed(int[] nums) {
            int curStealed = 0;
            int curUnStealed = 0;
            int preStealed = 0;
            int preUnStealed = 0;

            for (int i = 1; i < nums.length; i++) {
                curStealed = Math.max(preUnStealed + nums[i], preStealed);
                curUnStealed = Math.max(preStealed, preUnStealed);
                preStealed = curStealed;
                preUnStealed = curUnStealed;
            }
            return Math.max(curStealed, curUnStealed);
        }

    }
}
